//
// Created by shenbin on 2022/6/4.
//https://leetcode.cn/problems/relative-sort-array/submissions/
//

#ifndef ALGORITHM_TRAINNING_C04_LC1122_H
#define ALGORITHM_TRAINNING_C04_LC1122_H

#include <vector>
#include <unordered_map>

using namespace std;

class LeetCode1122 {
public:
    vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2) {
        unordered_map<int, int> arr2orders;
        for (int i = 0; i < arr2.size(); i++) {
            arr2orders[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [&](int x, int y) {
            int xPos = arr2orders.find(x) != arr2orders.end() ? arr2orders[x] : arr2.size();
            int yPos = arr2orders.find(y) != arr2orders.end() ? arr2orders[y] : arr2.size();
            return xPos < yPos || (xPos == yPos && x < y);
        });
        return arr1;
    }

    // 基于计数的排序
    vector<int> relativeSortArray2(vector<int> &arr1, vector<int> &arr2) {
        vector<int> count(1001, 0);
        for (int val: arr1) {
            count[val]++;
        }
        vector<int> ans;
        for (int val: arr2) {
            while (count[val] > 0) {
                ans.push_back(val);
                count[val]--;
            }
        }
        for (int val = 0; val <= 1000; val++) {
            while (count[val] > 0) {
                ans.push_back(val);
                count[val]--;
            }
        }
    }
};


#endif //ALGORITHM_TRAINNING_C04_LC1122_H
